/*--- bose-nel.c -------------------------- Listing 5-19 --------
 * Generate swap pairs based on the Bose-Nelson
 * technique, using the algorithm described by T. N.
 * Hibbard in A Simple Sorting Algorithm, Journal of
 * the ACM 10:142-50, 1963. The code is a direct
 * translation of Hibbard's pseudocode into C, and
 * retains his variable names, line labels, and use
 * of goto statements.
 *
 * Has built-in driver
 *-------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

/* common variables */
int SwapPairs = 0; /* running total of number of swap pairs */
FILE *OutFile;	   /* write swap pairs to this file */

/* Bit access macros */
#define SetBit(x,b) ((x) |=  (1 << (b)))
#define ClrBit(x,b) ((x) &= ~(1 << (b)))
#define TstBit(x,b) ((x) &   (1 << (b)))

void BoseSort(int N)
{
    unsigned int x, xj, y, yj, j, L;

    fprintf(OutFile, "{ /* Bose-Nelson sort for %d elements */\n", N);

    /* L = ceil(log2(N-1)) */
    L = sizeof(int) * CHAR_BIT - 1;
    for ( ; !TstBit(N - 1, L); L--)
        ;
    L += 1;

    /* starting values */
    x = 0;
    y = 1;

  /* Top of loop - x and y are a swap pair */
  A:                        /*--- goto target ---*/
    fprintf(OutFile, "    swap(%d, %d);\n", x, y);
    SwapPairs += 1;

    j = 0;

  C:                        /*--- goto target ---*/
    xj = TstBit(x, j);
    yj = TstBit(y, j);

    if (xj == 0 && yj == 0)
        goto zero;
    else if (xj && yj)
        goto one;
    else if (xj == 0)
        goto first_two;
    else
        goto two;

  zero:                     /*--- goto target ---*/
    SetBit(x, j);
    SetBit(y, j);
    if (y <= N - 1)
        goto A;

  one:                      /*--- goto target ---*/
    ClrBit(y, j);
    goto A;

  two:                      /*--- goto target ---*/
    ClrBit(x, j);
    j += 1;
    goto C;

  first_two:                /*--- goto target ---*/
    ClrBit(x, j);
    ClrBit(y, j);
    if (j == L)
        return;
    j += 1;
    if (TstBit(y, j))
        goto D;
    SetBit(x, j);
    SetBit(y, j);
    if (y > N - 1)
        goto first_two;
    if (y < N - 1)
        j = 0;

  D:                        /*--- goto target ---*/
    ClrBit(x, j);
    SetBit(y, j);
    goto A;
}

int main(int argc, char *argv[])
{
    int i, n;
    double optimal = 0.0;

    if (argc != 3 || (n = atoi(argv[1])) <= 1) {
        fprintf(stderr, "Usage: bose-nel N outfile, where N > 1\n");
        return (EXIT_FAILURE);
	}

    if ((OutFile = fopen(argv[2], "w")) == NULL) {
        fprintf(stderr, "Can't open %s\n", argv[2]);
        return (EXIT_FAILURE);
	}

    BoseSort(n);

    fprintf(OutFile, " } /* There are %d swaps */\n", SwapPairs);
    fclose(OutFile);

    printf("There were %d swaps generated.\n", SwapPairs);

	/*
	 * Report theoretical optimum.
	 * Start by computing log10(n!)
	 */
    for (i = 1; i <= n; i++)
        optimal += log10(i);

	/*
	 * Convert to ceil(log2(n!)) using
	 * fact that log10(2) = .30103
	 */
    optimal = ceil(optimal / 0.30103);

    printf("The best theoretical sort uses %.0f swaps.\n", (float)optimal);

    return (EXIT_SUCCESS);
}
